﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class _69Sqrt_x_ : IRun
    {
        /*
         * 计算并返回 x 的平方根，其中 x 是非负整数。
         * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
         * 示例 1:
         * 输入: 4
         * 输出: 2
         * 
         * 示例 2:
         * 输入: 8
         * 输出: 2
         * 
         * 说明: 8 的平方根是 2.82842..., 
         * 
         * 由于返回类型是整数，小数部分将被舍去。
         */

        /*
         * 解题思路：
         * 1、题目要求，返回类型为整数，小数部分舍去；
         * 2、可通过暴力破解，从1(i)开始算平方值；
         *    若等于，即返回i；
         *    若大于，即返回 i - 1;
         * 3、优化，通过二分法，减少搜索范围；
         *    若中间数值的平方值，大于输入值，则后方的数值，肯定大于；
         *    若中间数值的平方值，小于输入值，则前方的数值，肯定小于；
         */
        public void Run()
        {
            int _Result = MySqrt(2147483647);
        }

        public int MySqrt(int x)
        {
            int i = 1;
            long _Product;
            while (true)
            {
                _Product = (long)i * (long)i;
                if (_Product == x)
                    return i;
                else if (_Product > x)
                    return i - 1;
                i++;
            }
        }

        public int MySqrt1(int x)
        {
            long _low = 0;
            long _High = x;
            long _Mid;
            long _Product;
            while (_low < _High)
            {
                _Mid = (_low + _High) / 2;

                _Product = _Mid * _Mid;
                if (_Product > x)
                    _High = _Mid - 1;
                else if (_Product == x)
                    return (int)_Mid;
                else if (_Product < x)
                    _low = _Mid + 1;
            }

            if (_low * _low > x)
                return (int)(_low - 1);
            return (int)_low;
        }
    }
}
